"""
分解 合并
"""
import random


def mergeSort(nums):
    if not nums:
        return nums
    mid_index = len(nums) // 2

    if len(nums) <= 1:
        return nums

    # 分解
    l_nums = mergeSort(nums[:mid_index])
    r_nums = mergeSort(nums[mid_index:])

    # 合并
    l_index, r_index, result = 0, 0, []

    while l_index < len(l_nums) and r_index < len(r_nums):
        if l_nums[l_index] < r_nums[r_index]:
            result.append(l_nums[l_index])
            l_index += 1
        else:
            result.append(r_nums[r_index])
            r_index += 1

    # 添加剩余
    result += l_nums[l_index:]
    result += r_nums[r_index:]

    return result


if __name__ == '__main__':
    ls = [random.randint(1, 100) for _ in range(10)]
    print(ls)
    print(sorted(ls))
    print(mergeSort(ls))

    
